package com.yogurt.leetcode.circulate;

import java.util.HashMap;
import java.util.Map;

/**
 * 好数对的数目
 *
 * 给你一个整数数组 nums 。
 * 如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
 * 返回好数对的数目。
 *
 * 示例 1：
 * 输入：nums = [1,2,3,1,1,3]
 * 输出：4
 * 解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
 *
 * 示例 2：
 * 输入：nums = [1,1,1,1]
 * 输出：6
 * 解释：数组中的每组数字都是好数对
 *
 * 示例 3：
 * 输入：nums = [1,2,3]
 * 输出：0
 *
 * 提示：
 * 1 <= nums.length <= 100
 * 1 <= nums[i] <= 100
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 s = new Solution2();
        int nums[] = {1,2,3,1,1,3};
//        int nums[] = {1,1,1,1};
//        int nums[] = {1,2,3};
        System.out.println(s.numIdenticalPairs(nums));
    }
    public int numIdenticalPairs(int[] nums) {
        // 方式一：暴力统计，双层for循环，遍历对比
//        int count = 0;
//        for(int i = 0; i < nums.length; i++) {
//            for(int j = i + 1; j <= nums.length - 1; j++) {
//                if (nums[i] == nums[j]) {
//                    count++;
//                }
//            }
//        }
//        return count;

        // 方式二：使用Hash表
//        int count = 0;
//        Map<Integer, Integer> map = new HashMap<>();
//        for (int num : nums) {
//            map.put(num, map.getOrDefault(num, 0) + 1);
//        }
//        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
//            Integer value = entry.getValue();
//            count += value * (value - 1) / 2;
//        }
//        return count;

        // 方式三：
        int ans = 0;
        //因为 1<= nums[i] <= 100  所以申请大小为100的数组
        //temp用来记录num的个数
        int[] temp = new int[100];
        /*
        从前面开始遍历nums
        假设nums = [1,1,1,1]    [1,2,3,1,1,3]
        第一遍
        temp是[0,0,0,0]         [0,0,0,0,0,0]
        ans+=0;                 ans+=0;
        temp[0]++;              temp[0]++;
        第二遍
        temp是[1,0,0,0]         [1,0,0,0,0,0]
        ans+=1;                 ans+=temp[2-1]=temp[1]=0; ans+=0
        temp[0]++;              temp[1]++
        第三遍
        temp=[2,0,0,0]          [1,1,0,0,0,0]
        ans+=2;                 ans+=temp[3-1]=temp[2]=0; ans+=0
        temp[0]++;              temp[2]++
        第四遍
        temp=[3,0,0,0]          [1,1,1,0,0,0]
        ans+=3;                 ans+=temp[1-1]=temp[0]=1; ans+=1; ans=1
        temp[0]++;              temp[0]++

                                第五遍
                                [2,1,1,0,0,0]
                                ans+=temp[1-1]=temp[0]=2; ans+=2; ans=1+2=3
                                temp[0]++
                                第六遍
                                [3,1,1,0,0,0]
                                ans+=temp[3-1]=temp[2]=1;ans+=1; ans=3+1=4
                                temp[2]++

                                [3,1,2,0,0,0]
        */
        for (int num : nums) {
            /*
            这行代码可以写成
            ans+=temp[num - 1];
            temp[num - 1]++;
            */
            ans += temp[num - 1]++;
        }
        return ans;
    }
}
